import { IHeap } from './types'
import ArrayList from '@/sources/ArrayList'


/**
 * 二叉堆 (分为大顶堆和小顶堆)
 */
export default class Heap<T = number> implements IHeap<T> {
    private al: ArrayList<T>;
    constructor(elements: Array<T> = [], public compartor = (a: T, b: T) => ((a as any) - (b as any))) {
        // 初始化动态数组
        this.al = new ArrayList<T>()
        // 批量创建元素
        this.al.createArray(elements)
        elements.length > 0 && this.heapify()
    }

    /**
     * 获取二叉堆数量
     */
    size() {
        return this.al.size()
    }

    /**
     * 判断二叉堆是否为空
     */
    isEmpty() {
        return this.size() === 0
    }

    /**
     * 清空二叉堆
     */
    clear() {
        this.al.clear()
    }


    /**
     * 添加元素
     * @param element 
     */
    add(element: T) {
        // 校验参数
        this.checkElement(element);
        // 添加元素
        this.al.add(element);

        // 上滤
        this.upper(this.size() - 1);
    }

    /**
     * 获取堆顶元素
     */
    get() {
        return this.al.get(0)
    }


    /**
     * 删除堆顶元素
     */
    remove() {
        // 获取该元素
        const oldVal = this.al.get(0);
        const sizes = this.size();

        // 最后一个元素上来和第一个元素交换
        this.al.array[0] = this.al.array[sizes - 1]
        // 最后一个元素清空
        this.al.array[sizes - 1] = undefined as any

        // 长度减1
        this.al.descSize();

        // 下滤
        this.down()
        // 返回要删除的元素
        return oldVal
    }

    /**
     * 替换堆顶元素
     * @param element 
     */
    replace(element: T) {
        // 获取该元素
        const oldVal = this.al.get(0);
        // 替换该元素
        this.al.set(0, element)
        // 下滤
        this.down()
        // 返回要删除的元素
        return oldVal
    }

    /**
     * 校验元素
     * @param element 
     */
    private checkElement(element: T) {
        if (element == null) throw new Error('元素不合法~~')
    }

    /**
     * 上滤
     * @param index 
     */
    private upper(index: number) {
        // debugger
        if (index <= 0) return;
        // 父元素的索引
        let parI = this.getParI(index);
        // 没有父元素
        if (parI < 0) return;

        while (parI >= 0) {
            // 父元素存在
            if (this.al.get(index) > this.al.get(parI)) {
                // 比父元素大，交换两个元素的位置
                this.al.swap(index, parI);
                // 改变parI和index
                index = parI
                parI = this.getParI(parI)
            } else {
                // 比父元素小，直接结束循环
                break;
            }
        }
    }

    /**
     * 下滤
     * @param index 
     */
    down(i = 0) {
        // 从i开始往下下滤

        // 获取大小
        const sizes = this.size();

        // 获取非叶子节点的数量, 下滤只要处理非叶子节点
        const half = sizes >> 1;
        // debugger
        // 直到i 等于 half
        while (i < half) {
            // 获取左右子节点的数量
            let lI = this.getLeftChild(i),
                rI = this.getRightChild(i);

            // 获取左右子节点中最大的
            const maxI = this.getMax(lI, rI);

            // 最顶的都大于左右中最大的，直接返回即可
            if (this.getMax(maxI, i) === i) {
                break;
            }

            // 交换位置
            this.al.swap(maxI, i)


            // 更改i
            i = maxI;

        }

    }


    /**
     * 批量建堆
     */
    heapify() {
        const sizes = this.size()
        // 1. 自上而下的上滤 （比作添加）[1, size)
        // for (let i = 1; i < sizes; i++) {
        // this.upper(i)
        // }


        // 2. 自下而上的下滤（比作删除）  从非叶子节点开始,从下往上做下滤处理， [size >> 1 - 1, 0]
        let i = (sizes >> 1) - 1
        for (; i >= 0; i--) {
            this.down(i)
        }

    }

    /**
     * 获取父元素的索引
     * @param i 
     */
    private getParI(i: number) {
        return ~~((i - 1) >> 1)
    }

    /**
     * 获取左子节点的索引
     * @param i 
     */
    private getLeftChild(i: number) {
        return ((i + 1) << 1) - 1
    }

    /**
     * 获取右子节点的索引
     * @param i 
     */
    private getRightChild(i: number) {
        return (i + 1) << 1
    }

    /**
     * 获取左右中的最大值
     * @param l 
     * @param r 
     */
    private getMax(l: number, r: number) {
        let ld = this.al.get(l)
        let rd = this.al.get(r);
        // 右边没有孩子的，返回左边
        if (rd == undefined || r >= this.size()) return l
        const i = this.compartor(ld, rd) > 0 ? l : r
        return i
    }

    /**
     * 
     * @param cb 
     */
    forEach(cb: (ele: T, i: number) => void) {
        this.al.forEach((e, i) => {
            cb(e, i!)
            return false
        })
    }

}